package com.example.utils.util.TreeNodeUtil;

import com.example.utils.util.HttpResult;
import com.example.utils.util.TreeNodeUtil.pojo.TreeNode;
import com.example.utils.util.TreeNodeUtil.utils.NaryTreeNode;
import com.example.utils.util.TreeNodeUtil.utils.TreeBuild;
import org.springframework.web.bind.annotation.GetMapping;
import org.springframework.web.bind.annotation.RequestMapping;
import org.springframework.web.bind.annotation.RestController;

import java.util.*;

/**
 * @Description
 * @ClassName TestController
 * @Author jiang_11445266119198
 * @Date 2022/11/20 12:40
 */
@RestController
@RequestMapping("/tree")
public class TestController {

    @GetMapping("/treeTest")
    public HttpResult treeTest(){

        // 模拟测试数据（通常为数据库的查询结果）
        List<TreeNode> treeNodeList = new ArrayList<>();
        treeNodeList.add(new TreeNode(1,0,"顶级节点A"));
        treeNodeList.add(new TreeNode(2,0,"顶级节点B"));
        treeNodeList.add(new TreeNode(3,1,"父节点是A"));
        treeNodeList.add(new TreeNode(4,2,"父节点是B"));
        treeNodeList.add(new TreeNode(5,2,"父节点是B"));
        treeNodeList.add(new TreeNode(6,3,"父节点的ID是3"));

        // 创建树形结构（数据集合作为参数）
        TreeBuild treeBuild = new TreeBuild(treeNodeList);
        // 原查询结果转换树形结构
        treeNodeList = treeBuild.buildTree();
        // AjaxResult：个人封装返回的结果体  "测试数据",treeNodeList)
        return HttpResult.newSuccess().add("测试数据",treeNodeList);
    }

    public static void main(String[] args) {
        // 模拟测试数据（通常为数据库的查询结果）
        List<TreeNode> treeNodeList = new ArrayList<>();
        treeNodeList.add(new TreeNode(1,0,"顶级节点A"));
        treeNodeList.add(new TreeNode(2,0,"顶级节点B"));
        treeNodeList.add(new TreeNode(3,1,"父节点是A"));
        treeNodeList.add(new TreeNode(4,2,"父节点是B"));
        treeNodeList.add(new TreeNode(5,2,"父节点是B"));
        treeNodeList.add(new TreeNode(7,4,"父节点是B"));
        treeNodeList.add(new TreeNode(12,7,"父节点是B"));
        treeNodeList.add(new TreeNode(8,4,"父节点是B"));
        treeNodeList.add(new TreeNode(9,4,"父节点是B"));
        treeNodeList.add(new TreeNode(10,5,"父节点是B"));
        treeNodeList.add(new TreeNode(11,5,"父节点是B"));
        treeNodeList.add(new TreeNode(6,3,"父节点的ID是3"));

        /*      1                   2
        *     3               4           5
        *    6             7  8  9      10 11
        *                 12
        */

        // 创建树形结构（数据集合作为参数）
        TreeBuild treeBuild = new TreeBuild(treeNodeList);
        // 原查询结果转换树形结构
        treeNodeList = treeBuild.buildTree();
        treeNodeList.forEach(f -> {
            System.out.println("f = " + f.toString());
            List<TreeNode> treeNodes = preOrder(f);
            treeNodes.forEach(fo -> {
                System.out.println("fo = " + fo.toString());
            });
        });
        System.out.println("---------------------");
        treeNodeList.forEach(f -> {
            System.out.println("f = " + f.toString());
            List<List<TreeNode>> lists = levelOrder(f);
            lists.forEach(a -> {
                a.forEach(s -> {
                    System.out.println(s.toString());
                });
                System.out.println();
            });
        });
        System.out.println("---------------------");
        // region
         /*       1
              2   3   4
            5 6   7   8 9
         */
        NaryTreeNode tree = new NaryTreeNode(1);
        tree.addChildNode(new NaryTreeNode(2));
        tree.addChildNode(new NaryTreeNode(3));
        tree.addChildNode(new NaryTreeNode(4));
        List<NaryTreeNode> childList = tree.getChildren();
        childList.get(0).addChildNode(new NaryTreeNode(5));
        childList.get(0).addChildNode(new NaryTreeNode(6));
        childList.get(1).addChildNode(new NaryTreeNode(7));
        childList.get(2).addChildNode(new NaryTreeNode(8));
        childList.get(2).addChildNode(new NaryTreeNode(9));
        for (int i : tree.preOrder()) {
            System.out.print(i + "  ");
        }
        System.out.println();
        for (int i : tree.postOrder()) {
            System.out.print(i + "  ");
        }
        System.out.println();
        for (List<Integer> i : tree.levelOrder()) {
            for (int a : i) {
                System.out.print(a + "  ");
            }
            System.out.println();
        }
        // endregion
    }

    /**
     * 先序遍历：根左右
     * 利用栈模拟递归调用
     * 将根结点压入栈中，当栈不空时执行：
     * 弹出栈中结点，将其放入结果队列中
     * 将该结点的孩子按照倒序依次放入栈中
     */
    public static List<TreeNode> preOrder(TreeNode treeNode) {
        Stack<TreeNode> stack = new Stack<>();
        LinkedList<TreeNode> pre = new LinkedList<>();
        if (treeNode == null) return pre;
        stack.add(treeNode);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            pre.add(node);
            Stack<TreeNode> reChildren = new Stack<>();
            reChildren.addAll(node.getChildren());
            while (!reChildren.isEmpty()) {
                stack.push(reChildren.pop());
            }

        }
        return pre;
    }

    /**
     * 层次遍历：
     * 利用队列模拟递归调用
     * 将根结点压入队中，当队不空时执行：
     * 获取当前队列长度，当迭代次数小于当前队列长度时：
     * 弹出当前队头结点，将其放入当前层的结果队列中
     * 将该结点的孩子依次放入队列中
     * 将当前层的结果队列放入结果队列中
     */
    public static List<List<TreeNode>> levelOrder(TreeNode treeNode) {
        List<List<TreeNode>> result = new ArrayList<>();
        if (treeNode == null) return result;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(treeNode);
        while (!queue.isEmpty()) {
            List<TreeNode> level = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                level.add(node);
                queue.addAll(node.getChildren());
            }
            result.add(level);
        }
        return result;
    }
}
